use super::check::check_coord_for_grid;
pub use crate::base::*;

use std::{
    cmp::Reverse,
    collections::{BinaryHeap, HashMap, HashSet, VecDeque},
    hash::Hash,
};

pub fn search_single_target_path(
    grid: &Grid,
    start: Coord,
    target: Coord,
) -> Result<Vec<Coord>, String> {
    check_coord_for_grid(grid, start)?;
    check_coord_for_grid(grid, target)?;

    let mut queue = VecDeque::new();
    let mut prev_coord_map = HashMap::new();

    queue.push_back(start);
    prev_coord_map.insert(start, None);

    while let Some(coord) = queue.pop_front() {
        if coord == target {
            let mut path = VecDeque::new();
            let mut cur_coord = target;
            while let Some(prev_coord) = prev_coord_map.get(&cur_coord).unwrap() {
                // Must used
                path.push_front(cur_coord);

                cur_coord = *prev_coord;
            }
            path.push_front(cur_coord);

            return Ok(path.into_iter().collect());
        }

        for next_coord in coord.adjacent_coords() {
            if grid.is_valid_coord(next_coord)
                && grid.cell(next_coord).unwrap().is_empty()
                && !prev_coord_map.contains_key(&next_coord)
            {
                prev_coord_map.insert(next_coord, Some(coord));
                queue.push_back(next_coord);
            }
        }
    }

    Err("Route Faild".to_string())
}

pub fn search_single_target_path_with_astar(
    grid: &Grid,
    start: Coord,
    target: Coord,
) -> Result<Vec<Coord>, String> {
    check_coord_for_grid(grid, start)?;
    check_coord_for_grid(grid, target)?;

    let mut heap = BinaryHeap::new();
    let mut prev_coord_map = HashMap::new();

    heap.push(Reverse(CoordDistance(
        start,
        0,
        start.manhattan_distance(&target),
    )));
    prev_coord_map.insert(start, None);

    while let Some(Reverse(CoordDistance(coord, dis_to_start, _))) = heap.pop() {
        if coord == target {
            let mut path = VecDeque::new();
            let mut cur_coord = target;
            while let Some(prev_coord) = prev_coord_map.get(&cur_coord).unwrap() {
                // Must used
                path.push_front(cur_coord);

                cur_coord = *prev_coord;
            }
            path.push_front(cur_coord);

            return Ok(path.into_iter().collect());
        }

        for next_coord in coord.adjacent_coords() {
            if grid.is_valid_coord(next_coord)
                && grid.cell(next_coord).unwrap().is_empty()
                && !prev_coord_map.contains_key(&next_coord)
            {
                prev_coord_map.insert(next_coord, Some(coord));
                let predict_dis_to_target = next_coord.manhattan_distance(&target);
                heap.push(Reverse(CoordDistance(
                    next_coord,
                    dis_to_start + 1,
                    predict_dis_to_target,
                )));
            }
        }
    }

    Err("Route Faild".to_string())
}

pub fn search_single_target_path_with_astar_show_expend(
    grid: &Grid,
    start: Coord,
    target: Coord,
) -> Result<(Vec<Coord>, HashSet<Coord>), String> {
    // check_coord_for_grid(grid, start)?;
    check_coord_for_grid(grid, target)?;

    let mut expend_coords = HashSet::new();
    let mut heap = BinaryHeap::new();
    let mut prev_coord_map = HashMap::new();

    expend_coords.insert(start);
    heap.push(Reverse(CoordDistance(
        start,
        0,
        start.manhattan_distance(&target),
    )));
    prev_coord_map.insert(start, None);

    while let Some(Reverse(CoordDistance(coord, dis_to_start, _))) = heap.pop() {
        if coord == target {
            let mut path = VecDeque::new();
            let mut cur_coord = target;
            while let Some(prev_coord) = prev_coord_map.get(&cur_coord).unwrap() {
                // Must used
                path.push_front(cur_coord);

                cur_coord = *prev_coord;
            }
            path.push_front(cur_coord);

            return Ok((path.into_iter().collect(), expend_coords));
        }

        for next_coord in coord.adjacent_coords() {
            if grid.is_valid_coord(next_coord)
                && grid.cell(next_coord).unwrap().is_empty()
                && !prev_coord_map.contains_key(&next_coord)
            {
                prev_coord_map.insert(next_coord, Some(coord));
                let predict_dis_to_target = next_coord.manhattan_distance(&target);
                heap.push(Reverse(CoordDistance(
                    next_coord,
                    dis_to_start + 1,
                    predict_dis_to_target,
                )));
                expend_coords.insert(next_coord);
            }
        }
    }

    Err("Route Faild".to_string())
}

pub fn search_multi_targets_path(
    grid: &Grid,
    start: Coord,
    targets: &[Coord],
) -> Result<HashSet<Coord>, String> {
    check_coord_for_grid(grid, start)?;
    for target in targets.iter() {
        check_coord_for_grid(grid, *target)?;
    }

    let mut targets: HashSet<_> = targets.into_iter().map(|c| c.clone()).collect();
    let mut starts = HashSet::new();
    starts.insert(start);

    let mut path = HashSet::new();

    while !targets.is_empty() {
        let mut queue = VecDeque::new();
        let mut prev_coord_map = HashMap::new();

        for start in starts.iter() {
            queue.push_back(*start);
            prev_coord_map.insert(*start, None);
        }

        let mut find_net = false;
        while let Some(coord) = queue.pop_front() {
            if targets.contains(&coord) {
                let mut cur_coord = coord;
                while let Some(prev_coord) = prev_coord_map.get(&cur_coord).unwrap() {
                    // Must used
                    path.insert(cur_coord);
                    starts.insert(cur_coord);

                    cur_coord = *prev_coord;
                }
                path.insert(cur_coord);
                starts.insert(cur_coord);

                targets.remove(&coord);
                find_net = true;
                break;
            }

            for next_coord in coord.adjacent_coords() {
                if grid.is_valid_coord(next_coord)
                    && grid.cell(next_coord).unwrap().is_empty()
                    && !prev_coord_map.contains_key(&next_coord)
                    && !path.contains(&next_coord)
                {
                    prev_coord_map.insert(next_coord, Some(coord));
                    queue.push_back(next_coord);
                }
            }
        }

        if !find_net {
            return Err("Route Faild".to_string());
        }
    }

    Ok(path)
}

pub fn search_multi_targets_path_with_astar(
    grid: &Grid,
    start: Coord,
    targets: &[Coord],
) -> Result<HashSet<Coord>, String> {
    check_coord_for_grid(grid, start)?;
    for target in targets.iter() {
        check_coord_for_grid(grid, *target)?;
    }

    let mut targets: HashSet<_> = targets.into_iter().map(|c| c.clone()).collect();
    let mut starts = HashSet::new();
    starts.insert(start);

    fn min_manhattan_distance_to_targets(coord: &Coord, coords: &HashSet<Coord>) -> i32 {
        coords
            .iter()
            .map(|t| t.manhattan_distance(coord))
            .min()
            .unwrap()
    }

    let mut path = HashSet::new();

    while !targets.is_empty() {
        let mut heap = BinaryHeap::new();
        let mut prev_coord_map = HashMap::new();

        for start in starts.iter() {
            heap.push(Reverse(CoordDistance(
                *start,
                0,
                min_manhattan_distance_to_targets(start, &targets),
            )));
            prev_coord_map.insert(*start, None);
        }

        let mut find_net = false;
        while let Some(Reverse(CoordDistance(coord, dis_to_start, _))) = heap.pop() {
            if targets.contains(&coord) {
                let mut cur_coord = coord;
                while let Some(prev_coord) = prev_coord_map.get(&cur_coord).unwrap() {
                    // Must used
                    path.insert(cur_coord);
                    starts.insert(cur_coord);

                    cur_coord = *prev_coord;
                }
                path.insert(cur_coord);
                starts.insert(cur_coord);

                targets.remove(&coord);
                find_net = true;
                break;
            }

            for next_coord in coord.adjacent_coords() {
                if grid.is_valid_coord(next_coord)
                    && grid.cell(next_coord).unwrap().is_empty()
                    && !prev_coord_map.contains_key(&next_coord)
                    && !path.contains(&next_coord)
                {
                    prev_coord_map.insert(next_coord, Some(coord));
                    let predict_dis_to_target =
                        min_manhattan_distance_to_targets(&next_coord, &targets);
                    heap.push(Reverse(CoordDistance(
                        next_coord,
                        dis_to_start + 1,
                        predict_dis_to_target,
                    )));
                }
            }
        }

        if !find_net {
            return Err("Route Faild".to_string());
        }
    }

    Ok(path)
}

struct CoordDistance(Coord, i32, i32);

impl PartialEq for CoordDistance {
    fn eq(&self, other: &Self) -> bool {
        (self.1 + self.2) == (other.1 + other.2)
    }
}

impl Eq for CoordDistance {}

impl Hash for CoordDistance {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        (self.1 + self.2).hash(state)
    }
}

impl PartialOrd for CoordDistance {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        (self.1 + self.2).partial_cmp(&(other.1 + other.2))
    }
}

impl Ord for CoordDistance {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        (self.1 + self.2).cmp(&(other.1 + other.2))
    }
}
